package cn.xaut.周赛.m226;

public class demo1745 {

    // 判断一个字符串是否为回文字符串——迭代解法
    static boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            
            if (s.charAt(i) != s.charAt(j))
                return false;
            
            i ++;
            j --;
        }
        return true;
    }

    // 判断一个字符串是否为回文字符串——递归解法
    static boolean isPalindrome2(String s) {
        
        // 递归终止条件
        int i = 0, j = s.length() - 1;
        if (i == j)
            return true;
        if (i + 1 == j)
            return s.charAt(i) == s.charAt(j);
        
        // 递归过程
        return s.charAt(i) == s.charAt(j) && isPalindrome2(s.substring(i + 1, j));
    }
    
    // 暴力解法
    public boolean checkPartitioning(String s) {
        
        for (int l = 1; l < s.length() - 1; l++) {
            for (int r = s.length() - 1; r > 0; r--) {
                if (l >= r)
                    break;
                String s1 = s.substring(0, l);
                String s2 = s.substring(l, r);
                String s3 = s.substring(r, s.length());
/*                System.out.println("----------------");
                System.out.println(s1 + " " + isPalindrome(s1));
                System.out.println(s2 + " " + isPalindrome(s2));
                System.out.println(s3 + " " + isPalindrome(s3));*/
                if (isPalindrome(s1) && isPalindrome(s2) && isPalindrome(s3))
                    return true;
            }
        }
        return false;
    }

    // todo: 动态规划
    public boolean checkPartitioning2(String s) {
        
        int len = s.length();
        // dp[i][j] 表示 s[i...j] 是否为回文串
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) 
            dp[i][i] = true;
        
        char[] cs = s.toCharArray();
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (cs[i] != cs[j]) {
                    dp[i][j] = false;
                } else {    // cs[i] == cs[j]
                    if (j - i < 3)  // 字符串长度为 1 或 2
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                } 
            }
        }

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                if (dp[0][i] && dp[i + 1][j] && dp[j + 1][len - 1])
                    return true;
            }
        }
        return false;
    }

    // 方法2 动态规划的优化写法
    public boolean checkPartitioning3(String s) {

        int len = s.length();
        // dp[i][j] 表示 s[i...j] 是否为回文串
        boolean[][] dp = new boolean[len][len];
        // dp 的初始化可以优化一下
        // s.toCharArray() 可以略微提升算法的效率
        // s.charAt(i) 每次都会检查数组下标是否越界，因此先转换成字符数组
        char[] cs = s.toCharArray();    
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if ( (i == j) || (i + 1 == j && cs[i] == cs[j] ) )
                    dp[i][j] = true;
                else
                    dp[i][j] = cs[i] == cs[j] && dp[i + 1][j - 1];
            }
        }

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                if (dp[0][i] && dp[i + 1][j] && dp[j + 1][len - 1])
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {

        // 测试算法所得结果是否正确
        System.out.println(new demo1745().checkPartitioning("abcbdd"));     // true
        System.out.println(new demo1745().checkPartitioning2("bcbddxy"));   // false
        
        
        // 测试回文字符串函数是否正确
//        System.out.println(isPalindrome2("a"));     // true
//        System.out.println(isPalindrome2("ab"));    // false 
//        System.out.println(isPalindrome2("aa"));    // true
//        System.out.println(isPalindrome2("aba"));   // true
//        System.out.println(isPalindrome2("abba"));  // true
//        System.out.println(isPalindrome2("abcb"));  // false

    }
}
